1
Các ánh xạ toán học và mô hình hóa dữ liệu
MATH002Lesson 3
00:00
Các ánh xạ toán học và mô hình hóa dữ liệu đóng vai trò như cây cầu nối giữa lý thuyết tập hợp trừu tượng và thực tế tính toán. Trong khuôn khổ này, một thuật toán hành động như một phép biến đổi chính xác, có định hướng, nơi đầu vào được cấu trúc sẽ được xử lý qua các chỉ dẫn cụ thể để tạo ra đầu ra đúng đắn. Điều này thiết lập nền tảng logic cho mọi phần mềm và kiến trúc cơ sở dữ liệu.

Các thuộc tính của một thuật toán

Một thuật toán là phương pháp giải quyết vấn đề từng bước, được đặc trưng bởi bảy trụ cột then chốt:

  • Đầu vào: Thuật toán nhận dữ liệu từ một tập hợp đã xác định.
  • Đầu ra: Thuật toán tạo ra một kết quả (lời giải) từ một tập hợp đã xác định.
  • Độ chính xác: Mỗi bước được nêu rõ ràng tuyệt đối.
  • Tính xác định: Kết quả trung gian là duy nhất và chỉ được xác định bởi đầu vào và các bước trước đó.
  • Tính hữu hạn: Quy trình kết thúc sau một số lượng hữu hạn các lệnh.
  • Tính đúng đắn: Đầu ra giải quyết vấn đề như mong muốn.
  • Tính tổng quát: Quy trình áp dụng cho một lớp các đầu vào, chứ không chỉ riêng một trường hợp.

Thuật toán 4.1.1: Tìm giá trị lớn nhất trong ba số

Mối quan hệ tam phân đơn giản này minh họa tính chính xác và tính xác định. Dù các giá trị của $a, b,$ và $c$ là gì, các bước vẫn tuân theo một con đường logic nghiêm ngặt.

Dòng suy luận giả mã
max3(a, b, c) {
    large = a
    nếu (b > large) large = b
    nếu (c > large) large = c
    trả về large
}

Mô hình hóa dữ liệu và các bất biến vòng lặp

Trong các cấu trúc dữ liệu phức tạp hơn, như dãy số ($s_1, ..., s_n$), chúng ta sử dụng Thuật toán 4.1.2. Để đảm bảo các thuật toán này đúng đắn, chúng ta dựa vào quy nạp và khái niệm về một bất biến vòng lặp.

Thuật toán 4.1.2: Tìm giá trị lớn nhất trong một dãy số
max(s, n) {
    large = s_1
    for i = 2 đến n
        nếu (s_i > large)
            large = s_i
    trả về large
}

Bất biến vòng lặp: "large là giá trị lớn nhất trong dãy con $s_1, ..., s_i$". Tính chất này luôn đúng qua mỗi lần lặp, chứng minh tính đúng đắn thông qua quy nạp.

🎯 Nguyên lý cốt lõi: Tính hợp lệ của ánh xạ
Một hàm toán học hợp lệ yêu cầu mỗi phần tử trong miền xác định phải ánh xạ tới chính xác một phần tử trong tập ảnh. Việc thiếu mũi tên hoặc nhiều mũi tên xuất phát từ cùng một nguồn sẽ làm mất tính hợp lệ của hàm, phản ánh lý do tại sao các thuật toán phi xác định hoặc chưa hoàn chỉnh thường thất bại trong thực tế.